package com.xj.datastructure.sort;

/**
 * author: xiajun
 * Date: 2014-07-19
 * Time: 14-47-00
 * 计数排序
 * 计数排序使用一个额外的数组C，
 * 其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。
 */
public class CountingSort {
    public static void main(String[] args) {
        int a[]={2,4,42,43,145,211};
        CountingSort sort=new CountingSort();
        sort.sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    public void sort(int[] a) {
        int max = 0;
        for (int i = 0; i < a.length; i++) {//找出数组中的最大值
            if (a[i] > max) {
                max = a[i];
            }
        }
        int[] c = new int[max+1];
        for (int i = 0; i < a.length; i++) {
            c[a[i]] = c[a[i]] + 1;
        }
        int j = 0;
        for (int i = 0; i < c.length; i++) {
            if (c[i] > 0) {
                for (int k=0;k<c[i];k++) {
                    a[j] = i;
                    j++;
                }
            }
        }
    }
}
